class hashTable {
  constructor() {
    this.storage = []
    this.count = 0
    this.limit = 7
  }
  hashFunc(str, size) {
    let hashCode = 0
    for (let i = 0; i < str.length; ++i) {
      hashCode = 37 * hashCode + str.charCodeAt(i)
    }
    return hashCode % size
  }
  // 插入和修改操作
  put(key, value) {
    const index = this.hashFunc(key, this.limit)
    //   先判断木桶是否存在
    let bucket = this.storage[index]
    if (!bucket) {
      bucket = []
      this.storage[index] = bucket
    }
    //   判断该木桶是否存在元素，存在就修改
    for (let i = 0; i < bucket.length; ++i) {
      if (bucket[i][0] === key) {
        bucket[i][1] === value
        return
      }
    }
    //   不存在就添加
    bucket.push([key, value])
    this.count += 1
    //扩大容量
    if (this.count > this.limit * 0.75) {
      this.resize(this.getNearestPrime(this.limit * 2))
    }
  }
  // 获取元素
  get(key) {
    const index = this.hashFunc(key, this.limit)
    let bucket = this.storage[index]
    if (bucket) {
      for (let i = 0; i < bucket.length; ++i) {
        if (bucket[i][0] === key) {
          return bucket[i][1]
        }
      }
    }
    return null
  }
  remove(key) {
    const index = this.hashFunc(key, this.limit)
    let bucket = this.storage[index]
    if (bucket) {
      for (let i = 0; i < bucket.length; ++i) {
        if (bucket[i][0] === key) {
          const value = bucket[i][1]
          bucket.splice(i, 1)
          this.count -= 1
          //缩小容量
          if (this.limit > 7 && this.count < this.limit * 0.25) {
            this.resize(this.getNearestPrime(Math.floor(this.limit / 2)))
          }
          return value
        }
      }
    }
    return null
  }
  isEmpty() {
    return this.count === 0
  }
  size() {
    return this.count
  }
  resize(newlimit) {
    const oldStorage = this.storage
    this.storage = []
    this.count = 0
    this.limit = newlimit
    for (let i = 0; i < this.oldStorage.length; ++i) {
      let bucket = this.oldStorage[i]
      if (bucket) {
        for (let j = 0; j < bucket.length; ++j) {
          this.put(bucket[j][0], bucket[j][1])
        }
      }
    }
  }
  // 判断一个数是否是质数
  isPrime(num) {
    for (let i = 2; i <= parseInt(Math.sqrt(num)); ++i) {
      if (num % i === 0) {
        return false
      }
    }
    return true
  }
  // 获取当前数向上最近的质数
  getNearestPrime(num) {
    let prime = num
    while (!this.isPrime(prime)) {
      prime++
    }
    return prime
  }
}
const hash = new hashTable()
hash.put('zjd', 18)
console.log(hash.get('zjd'))
console.log(hash.remove('zjd1'))
console.log(hash.isPrime(5))
console.log(hash.getNearestPrime(8))
